#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define StackSize 10

typedef struct stack
{
    char data[StackSize];
    int top; // 表示栈顶指针
} Stack, *SeqStack;

// 置空栈
void initStack(SeqStack s)
{
    if (s == NULL)
    {
        printf("error initializing seqstack, can't be null\n");
        exit(0);
    }

    s->top = -1;
}
// 判空栈
int stackEmpty(SeqStack s)
{
    return s->top == -1;
}
// 判满栈
int stackFull(SeqStack s)
{
    return s->top == StackSize - 1;
}
// 进栈
void push(SeqStack s, char x)
{
    if (stackFull(s))
    {
        printf("the seqstack is full\n");
        return;
    }

    s->top = s->top + 1;
    s->data[s->top] = x;
    printf("stack push>>%c\n", x);
}
// 退栈
char pop(SeqStack s)
{
    if (stackEmpty(s))
    {
        printf("the seqstack is empty, will exit\n");
        exit(0);
    }
    char x = s->data[s->top--];
    printf("stack pop>>%c\n", x);
    return x;
}

// 判断圆括号(字符串包含括号)是否匹配, 匹配则1，不匹配则0
int judgeBracket()
{
    SeqStack stack = (SeqStack)malloc(sizeof(Stack));
    initStack(stack);

    printf(">>>input char:");
    char ch;
    while ((ch = getchar()) != '\n')
    {
        printf("---------------%c\n", ch);
        if (ch == '(')
        {
            push(stack, ch);
        }
        else if (ch == ')')
        {
            if (stackEmpty(stack))
            {
                return 0;
            }

            pop(stack);
        }

        // 字符串中仅包含括号
        /*
        if (ch == '(')
        {
            push(stack, ')');
        }
        else if (stackEmpty(stack) || ch != pop(stack))
        {
            return 0;
        }
        */
    }

    return stackEmpty(stack);
}

// 字符串回文判断. 实际看起来没必要用堆栈. 是回文1，不是0
int judgeSymmetryStr(char *ch)
{
    SeqStack stack = (SeqStack)malloc(sizeof(Stack));
    initStack(stack);

    // char ch[]={}; int len=0; while(ch[len] != '\0') len++;
    int len = strlen(ch);
    // 前半段字符
    for (int i = 0; i < len / 2; i++)
    {
        //    printf("ch=%c\n", ch[i]);
        push(stack, ch[i]);
    }

    // 后半段字符， (len + 1)/2 解决奇数问题整取
    for (int j = (len + 1) / 2; j < len; j++)
    {
        if (ch[j] != pop(stack))
        {
            return 0;
        }
    }

    // 不用堆栈解决
    /*
    for (int i = 0; i < len / 2; i++)
    {
        if (ch[i] != ch[len - 1 - i])
        {
            return 0;
        }
    }
    */

    return 1;
}

// 非负(十进制)整数N转换为任意进制数. 进制公式 N=(N/d)*d + N%d; 循环整除，结果为取余的倒序
void conversion(int N, int d)
{
    SeqStack stack = (SeqStack)malloc(sizeof(Stack));
    initStack(stack);

    // 循环取整直至为0
    while (N)
    {
        // 取余
        push(stack, N % d);
        N = N / d;
    }

    // 出栈。 C 语言的字符串拼接有点麻烦
    while (!stackEmpty(stack))
    {
        int x = pop(stack);
        printf("%d\n", x);
    }
}

// 阶乘递归函数。 long int 最大范围整型
long int factorial(int n)
{
    long int temp;
    if (n == 0)
    {
        return 1;
    }
    temp = n * factorial(n - 1);
    return temp;
}

int main()
{
    // printf("judge bracket whether match: %s\n", judgeBracket() ? "YES" : "NO");
    // char *cc = "abccba";
    // printf("judge str whether symmetry: %s\n", judgeSymmetryStr(cc) ? "YES" : "NO");
    // conversion(3353, 8);
    // exit(0);

    SeqStack stack = (SeqStack)malloc(sizeof(Stack));
    initStack(stack);

    // char ch1[] = {'a', 'b', 'c', 'd', '\0'}; // 方式①
    // printf("==char array len=%lu\n", sizeof(ch1));
    char *ch = "abcd"; // 方式②
    int len = strlen(ch);
    printf("-----------seqstack push----------size=%d\n", len);
    // for (int i = 0; i < len; i++)
    // {
    //     push(stack, ch[i]);
    // }
    char in;
    while ((in = getchar()) != '\n')
    {
        push(stack, in);
    }

    printf("----------seqstack pop-------------\n");
    // for (int i = 0; i < len; i++)
    // {
    //     printf("stack pop>> %c\n", pop(stack));
    // }
    while (!stackEmpty(stack))
    {
        printf("stack pop>> %c\n", pop(stack));
    }

    return 0;
}